import java.awt.Point;
import java.util.LinkedList;
import java.util.List;

/**
 * An implementation of the Bresenham algorithm. The algorithm is used to find
 * all points on a straight line between a start and end point.
 * 
 * @author Emanuel Yifter Lindgren (dv11elr), Anders Lumio (dv11alo)
 *
 */
public class BresenhamAlgorithm {

    /**
     * Calculates and returns a list of Points between the start and endpoint.
     * 
     * @param x1
     *            x-coordinate of startpoint.
     * @param y1
     *            y-coordinate of startpoint.
     * @param x2
     *            x-coordinate of endpoint.
     * @param y2
     *            y-coordinate of endpoint.
     * 
     * @return the sequence of points along the straight line between the start
     *         and endpoint.
     */
    public static List<Point> getLine(final int x1, final int y1, final int x2,
            final int y2) {
        return createLine(x1, y1, x2, y2);
    }

    private static List<Point> createLine(int x, int y, final int x2,
            final int y2) {
        final LinkedList<Point> line = new LinkedList<Point>();

        final int w = x2 - x;
        final int h = y2 - y;
        int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0;
        if (w < 0) {
            dx1 = -1;
        } else if (w > 0) {
            dx1 = 1;
        }
        if (h < 0) {
            dy1 = -1;
        } else if (h > 0) {
            dy1 = 1;
        }
        if (w < 0) {
            dx2 = -1;
        } else if (w > 0) {
            dx2 = 1;
        }
        int longest = Math.abs(w);
        int shortest = Math.abs(h);
        if (!(longest > shortest)) {
            longest = Math.abs(h);
            shortest = Math.abs(w);
            if (h < 0) {
                dy2 = -1;
            } else if (h > 0) {
                dy2 = 1;
            }
            dx2 = 0;
        }
        int numerator = longest >> 1;
        for (int i = 0; i <= longest; i++) {
            line.add(new Point(x, y));
            numerator += shortest;
            if (!(numerator < longest)) {
                numerator -= longest;
                x += dx1;
                y += dy1;
            } else {
                x += dx2;
                y += dy2;
            }
        }
        return line;
    }
}
